package common

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//使用递归是nlogn的复杂度
func (t *TreeNode) PreOrder_Traver() []int {
	var res []int
	if t == nil {
		return res
	}

	res = append(res, t.Val)
	if t.Left != nil {
		res = append(res, t.Left.PreOrder_Traver()...)
	}

	if t.Right != nil {
		res = append(res, t.Right.PreOrder_Traver()...)
	}
	return res
}

// 中序在遍历bst时可以得到排序后的数组
func (t *TreeNode) InOrder_Traver() []int {
	var res []int
	if t == nil {
		return res
	}

	if t.Left != nil {
		res = append(res, t.Left.InOrder_Traver()...)
	}
	res = append(res, t.Val)
	if t.Right != nil {
		res = append(res, t.Right.InOrder_Traver()...)
	}
	return res
}

func (t *TreeNode) PostOrder_Traver() []int {
	var res []int
	if t == nil {
		return res
	}

	if t.Left != nil {
		res = append(res, t.Left.PostOrder_Traver()...)
	}
	if t.Right != nil {
		res = append(res, t.Right.PostOrder_Traver()...)
	}
	res = append(res, t.Val)
	return res
}

// 广度优先
func (t *TreeNode) Layer_Traver() []int {
	var res []int
	head, tail := 0, 0

	var p []*TreeNode
	var tmp *TreeNode

	if t != nil {
		p = append(p, t)
		res = append(res, t.Val)
		tail++
	} else {
		return res
	}

	//使用双指针
	for head < tail {
		tmp = p[head] // 队列，先进先读取，就用普通数组就OK了
		if tmp.Left != nil {
			p = append(p, tmp.Left)
			res = append(res, tmp.Left.Val)
			tail++
		}
		if tmp.Right != nil {
			p = append(p, tmp.Right)
			res = append(res, tmp.Right.Val)
			tail++
		}
		head++
	}
	return res
}

//插入构建二叉查找树  （左子数的所有键值小于其根节点的键值，右子树的所有键值大于其根节点的键值
func (t *TreeNode) Insert(value int) *TreeNode {
	if t == nil {
		return &TreeNode{value, nil, nil}
	} else {
		if t.compare(value) > 0 {
			t.Left = t.Left.Insert(value)
		} else if t.compare(value) < 0 {
			t.Right = t.Right.Insert(value)
		}
	}
	return t
}

func (t *TreeNode) compare(value int) int {
	if t.Val > value {
		return 1
	} else if t.Val == value {
		return 0
	} else {
		return -1
	}
}

// 最大深度，这个需要记住，感觉直接用递推的方式也不靠谱
func (t *TreeNode) MaxDepth() int {
	if t == nil {
		return 0
	}
	left := t.Left.MaxDepth()
	right := t.Right.MaxDepth()

	if left > right {
		return left + 1
	} else {
		return right + 1
	}
}

// 最小深度
func (t *TreeNode) MinDepth() int {
	if t == nil {
		return 0
	}

	// 这里是需要注意的坑
	if t.Left == nil {
		return t.Right.MinDepth() + 1
	}
	if t.Right == nil {
		return t.Left.MinDepth() + 1
	}

	left := t.Left.MinDepth()
	right := t.Right.MinDepth()
	if left < right {
		return left + 1
	} else {
		return right + 1
	}
}
